#include"encode.h"
#include"constant.h"
#include"freq.h"
#include"list.h"
#include"tree.h"
#include"utility.h"
#include<stdio.h>
#include<strings.h>
#include<stdlib.h>

int encode(char * infile,char * outfile,int mode){

    CharFreq frequencies[NUMLETTER];
    bzero(frequencies,sizeof(CharFreq)*NUMLETTER);
    // -从文件读取字符集并记录下字符的频率
    if(countFrequency(infile,frequencies) == 1){

        return 0;
    }
    // -根据频率对字符集进行排序
    sortFrequency(frequencies);

    // ~test~
    // for(int index = NUMLETTER-1;index >= 0;index--){

    //     if(0 == frequencies[index].freq){

    //         break;
    //     }
    //     printf("value = %c,freq = %d.\n",frequencies[index].value,frequencies[index].freq);
    // }
    // ~test~
    ListNode * head = ListNode_build(frequencies);

    // ~test~
    ListNode * ptr = head;
    while (ptr)
    {
        ListNode_print(ptr);
        ptr = ptr->next;
    }    
    // ~test~
    if(NULL == head){
        return 0;
    }
    // -合并到只剩下一个节点（合并节点）
    while(head->next!=NULL){

        // TreeNode * left = head->tnptr;
        // List_print(head);   printf("------------.\n");
        ListNode * second = head->next;
        ListNode * third = second->next;

        TreeNode * tn1 = head->tnptr;
        TreeNode * tn2 = second->tnptr;

        free(head);
        free(second);
        head = third;

        TreeNode * mrg = TreeNode_merge(tn1,tn2);
        ListNode * ln = ListNode_create(mrg);
        head = ListNode_insert(head,ln);
    }
    // -下一部分就是构建编码之后对应之后
    TreeNode * root = head->tnptr;
    free(head);
    
    // Tree_print(root,0);
    int numRow = Tree_leaf(root);
    int numCol = Tree_height(root);

    // -numCol应该加1，来容纳最后的-1
    numCol++;
    int ** codebook = malloc(sizeof(int*)*numRow);
    for(int row = 0;row < numRow;row++){

        codebook[row] = malloc(sizeof(int)*numCol);
        // -初始化为-1
        for(int index = 0;index < numCol;index++){

            codebook[row][index] = -1;
        }
    }
    // Tree_print(root,0);
    buildCodeBook(root,codebook);
    printCodeBook(codebook,numRow);

    // -contining
    Tree_header(root,outfile);

    int mapping[NUMLETTER];
    for(int index = 0;index < NUMLETTER;index++){

        mapping[index] = -1;
        for(int index2 = 0;index2 < numRow;index2++){

            // -根据字符对应的ascii码映射到mapping上
            if(codebook[index2][0] == index){

                mapping[index] = index2;
            }
        }
    }
    compress(infile,outfile,codebook,mapping);
    return 1;
}

void buildCodeBook(TreeNode * root,int ** codebook){

    int row = 0;
    // -从第0行第1列开始
    buildCodeBookHelper(root,codebook,&row,1);
}

void printCodeBook(int ** codebook,int numRow){
    int row;
    for(row = 0;row < numRow;row++){
        // 打印字符
        printf("%c: ",(char)codebook[row][0]);
        int col = 1;
        while(codebook[row][col]!=-1){

            printf("%d ",codebook[row][col]);
            col++;
        }
        printf("\n");
    }
}
static int Tree_heightHelper(TreeNode * tn,int height){

    if(0 == tn){

        return height;
    }
    int lh = Tree_heightHelper(tn->left,height+1);
    int rh = Tree_heightHelper(tn->right,height+1);

    if(lh > rh){

        return lh;
    }
    if(rh > lh){

        return rh;
    }
    // lh == rh
    return rh;
}
// -计算节点tn的高度
int Tree_height(TreeNode * tn){

    return Tree_heightHelper(tn,0);
}

/////////////////////////////////////////////

static void Tree_leafHelper(TreeNode * tn,int * num){

    if(NULL == tn){

        return;
    }
    TreeNode * lc = tn->left;
    TreeNode * rc = tn->right;
    if((NULL == lc) && (NULL == rc)){

        (*num)++;
        return;
    }
    Tree_leafHelper(lc,num);
    Tree_leafHelper(rc,num);
}
// -计算节点tn的叶子节点
int Tree_leaf(TreeNode * tn){

    int num = 0;
    Tree_leafHelper(tn,&num);
    return num;    
}


// -
void buildCodeBookHelper(TreeNode * tn,int ** codebook,int * row,int col){

    if(NULL == tn){

        return;
    }
    TreeNode * lc = tn->left;
    TreeNode * rc = tn->right;

    // -叶子节点带有字符的
    if(lc == NULL && rc == NULL){

        codebook[*row][0] = tn->value;
        (*row)++;
    }

    if(NULL!=lc){

        int numRow = Tree_leaf(lc);
        int index = 0;
        // -根节点的左节点的子叶
        for(index = (*row);index < (*row) + numRow;index++){

            codebook[index][col] = 0; 
        }
        buildCodeBookHelper(lc,codebook,row,col+1);
    }
    // -到达右边基本上已经把根节点左边的叶子节点去掉了。
    if(NULL!=rc){

        int numRow = Tree_leaf(rc);
        int index = 0;
        for(index = (*row);index < (*row) + numRow;index++){

            codebook[index][col] = 1;
        }
        buildCodeBookHelper(rc,codebook,row,col+1);
    }
}